//https://leetcode.cn/problems/minimum-number-of-changes-to-make-binary-string-beautiful/description/


class Solution {
public:
    int count(const string &s,int l, int r, int x)
    {
        int ret = 0;
        for (int i = max(1, l); i <= r; i++) 
            if (s[i - 1] - '0' == x) ret++;
        return ret;
    }

    int minChanges(string s) {
        //f(i)表示将前 i 个字符构成的子串变得美丽，且第i个字符是 0 的最少修改次数;1->0
        //g(i)表示将前 i 个字符构成的子串变得美丽，且第i个字符是 1 的最少修改次数;0->1
        int n = s.size();
        vector<int> f(n + 1), g(n + 1);
        f[0] = g[0] = 0;
        for(int i = 0; i + 2 <= n; i++)
        {
            int one = count(s, i + 1, i + 2, 1);
            int zero = count(s, i + 1, i + 2, 0);
            f[i + 2] = min(f[i], g[i]) + one;
            g[i + 2] = min(f[i], g[i]) + zero;
        }
        return min(f[n], g[n]);
    }
};